ABSTRACT
Due to the COVID-19 pandemic and the shortage of vaccinations during its roll-out, the question regarding the best strategy to achieve immunity in the population by adjusting the time between the two necessary vaccination doses was intensively discussed. This strategy has already been studied from various angles by various researches. However, the combinatorial optimization problem and its complexity has not been the focus of attention. In this paper, we study the complexity of different versions of this problem by first proposing a simple approach using a matching algorithm. Then, we extend the approach by adding constraints and multiple manufacturers. Finally, we discuss a variation of the problem where three vaccinations are necessary, including the so-called "booster". This problem turns out to be NP-hard.